package leetcode;

public class IsPowerOfThree {

	public static void main(String[] args) {
		IsPowerOfThree three = new IsPowerOfThree();
		System.out.println(three.isPowerOfThree(1162261470));
	}
	
	//要处理溢出的问题，不太好
	//20ms
	public boolean isPowerOfThree(int n) {
		if (n == 1) {
			return true;
		}
		int target = 1;
		for (; target < n;) {
			if(target  <= Integer.MAX_VALUE / 3){
				target = target * 3;
			}else {
				break;
			}
			if(target == n){
				return true;
			}
		}
		return target == n;
	}
	
	//19ms
	public boolean isPowerOfThree2(int n) {
		if(n > 1){
			while(n % 3 == 0){
				n /= 3;
			}
		}
		return n == 1;
	}
	
	//计算出最大的3的幂
	public boolean isPowerOfThree3(int n){
		int maxPowerOfThree = 1162261467;
		return n > 0 && maxPowerOfThree % n ==0;
	}
	
//	public boolean isPowerOfFour(int n){
//		int maxPowerOfThree = 1073741824;
//		//错了，这样只能判断是否是2的幂
//		return n > 0 && maxPowerOfThree % n ==0;
//	}
	
	public boolean isPowerOfFour(int n){
		//还有一种方法：
		//return ((num-1)&num)==0 && (num-1)%3==0;
		
		//(n & (n - 1)) == 0表示是二的幂
		//5:0101、1刚好割了1位，比如4： 100， 8 1000，16 ：10000
		//因为4的幂相当于左移两位，所以与0x55555555进行与运算，如果结果与n相等就说明是4的幂次
		return n > 0 && ((n & (n - 1)) == 0) && (n & 0x55555555) == n;
	}
}
